package com.cuz.daileetcode.utils;

public class KMP {

    public static void main(String[] args) {
        String str1 = "ababcad";
        String str2 = "cad";
        System.out.println(indexOf(str1, str2));
        System.out.println(str1.indexOf(str2));
    }

    public static int indexOf(String source, String target) {
        //baseCase 无需多言
        if (source == null || target == null
                || source.length() == 0 || target.length() == 0
                || source.length() < target.length()) {
            return -1;
        }
        //拿到辅助数组，记录和每一个字符之前的最长前缀后缀
        int[] prefixSuffixMaxArray = prefixSuffixMaxArray(target);
        //原字符串比较起始index
        int sourceIndex = 0;
        //查找字符串起始index
        int targetIndex = 0;
        char[] sourceCharArray = source.toCharArray();
        char[] targetCharArray = target.toCharArray();
        //首先不能越界哈
        while (sourceIndex < source.length() && targetIndex < target.length()) {
            //如果相等那么 一起前进
            //比如 source  ：      abcabcdabcabcde
            //比如 target  ：      abcabcde
            //前 target从0到  6都是和 source 0 到6都是相等 那么自增
            if (sourceCharArray[sourceIndex] == targetCharArray[targetIndex]) {
                sourceIndex++;
                targetIndex++;
            } else {
                //如：source =aaaaad
                //如：target =ad 第一次不等发生在 targetIndex=1
                //prefixSuffixMaxArray[1]=0 进入else  targetIndex = prefixSuffixMaxArray[1]=0;
                //下次进入循环prefixSuffixMaxArray[0]=-1 sourceIndex++
                //sourceIndex++ 意味着什么，1下标 之前在source串已经不存有子串和 target匹配了
                //所有source+1 从下一个开始和target匹配
                if (prefixSuffixMaxArray[targetIndex] == -1) {
                    sourceIndex++;
                } else {
                    //比如source：ababad
                    //target：   abad
                    //targetIndex=3的时候不等 prefixSuffixMaxArray[3]=1 targetIndex=1 在进行匹配
                    targetIndex = prefixSuffixMaxArray[targetIndex];
                }
            }
        }
        //targetIndex 和 sourceIndex 必定有一个越界才可以循环结束
        //如果target匹配完了 返回 sourceIndex - targetIndex
        //也就是targetIndex 越界 代表找到了
        if (targetIndex == target.length()) {
            return sourceIndex - targetIndex;
        }
        //sourceIndex 找到越界了 也没有找到
        return -1;
    }

    private static int[] prefixSuffixMaxArray(String str) {
        //如果 长度为0 那么直接返回-1
        if (str.length() == 0) {
            return new int[]{-1};
        }
        //定义一个辅助数组 长度等于字符串 的长度
        int[] helpArray = new int[str.length()];
        //人为定义
        helpArray[0] = -1;
        helpArray[1] = 0;
        //下一个要求解最长前后缀串长度的字符
        int index = 2;
        //需要比较的字符，注意index=2 的时候要比较 index-1也就是1 和 0是否相对 如果相等那么1
        //对于index=3 4 5 等 比较自己和前一个字符在helpArray中的值对于的字符是否相等 相等+1
        //如 abcab？ 对于？号处的字符,前一个字符为b 其最长前后缀字符串长度为2
        //2 对于的字符是 c 如果？ 等于c 那么 help[5(？下标)]=help[4(？前一个字符下标)]+1
        int preCharIndex = 0;
        char[] charArray = str.toCharArray();
        while (index < str.length()) {
            //如 abcab？ 对于？号处的字符,前一个字符为b 其最长前后缀字符串长度为2
            //2 对于的字符是 c 如果？ 等于c 那么 help[5(？下标)]=help[4(？前一个字符下标)]+1
            if (charArray[index - 1] == charArray[preCharIndex]) {
                helpArray[index] = preCharIndex + 1;
                //当前要比较的字符为值++
                index++;
                //可以参考的字符下标也++
                preCharIndex++;
            } else {
                //如果不等 且 preCharIndex  什么意思
                //如：
                //ababdabax？ 对于？前一个字x最长前后缀长度为aba为3 charArray[3]为b！=x
                //so preCharIndex=3 下一次循环进来 比较假设x字符为b（ababdabab？） 那么
                //charArray[？的下标 - 1] == charArray[3] 那么helpArray[？的下标]=4 因为存在abab呀
                if (preCharIndex > 0) {
                    preCharIndex = helpArray[preCharIndex];
                } else {
                    //加入x为c ababdabac？ preCharIndex=3 还是不等（指第一个if 不能进去）
                    //preCharIndex>0  preCharIndex = helpArray[3](问b的最长前后缀长度 为 a so 1)
                    //preCharIndex=1
                    //再次进入循环  还是不等（指第一个if 不能进去）
                    //preCharIndex>0  preCharIndex = helpArray[1] preCharIndex=0
                    //最后就会到这里面了  helpArray[index] = 0; 指没有最长前后缀为0
                    helpArray[index] = 0;
                    index++;
                }
            }
        }
        return helpArray;
    }
}
